// @algorithm @lc id=301 lang=cpp 
// @title remove-invalid-parentheses


#define print(...)
// @test("()())()")=["()()()","(())()"]
// @test("(a)())()")=["(a)()()","(a())()"]
// @test(")(")=[""]
using it_t = string::iterator;
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        print("\nins=", s, "\n")
        int dL = 0, dR = 0;
        for(auto & c : s){
            switch(c){
            case '(':
                ++ dL;
                break;
            case ')':
                0 < dL ? dL-- : dR++;
                break;
            }
        }
        unordered_set<string> res;
        string ans(s.size(), '\0');
        function<void(it_t,int,int,int,int,int)> dfs =
        [&](it_t it, int n, int nL, int nR, int dL, int dR){
            if(it == s.end()){
                if(0==dL && 0==dR)
                    res.insert(ans.substr(0, n));
                print("may:", ans.substr(0, n), "|dL=", dL, ", dR=", dR, "\n")
                return;
            }
            switch(*it){
            case '(':
                if(dL>0)
                    dfs(it+1, n, nL, nR, dL-1, dR);
                ans[n] = *it;
                dfs(it+1, n+1, nL+1, nR, dL, dR);
                break;
            case ')':
                if(dR>0)
                    dfs(it+1, n, nL, nR, dL, dR-1);
                if(nL > nR){
                    ans[n] = *it;
                    dfs(it+1, n+1, nL, nR+1, dL, dR);
                }
                break;
            default:
                ans[n] = *it;
                dfs(it+1, n+1, nL, nR, dL, dR);
                break;
            }
        };
        dfs(s.begin(),0, 0, 0, dL, dR);
        print("ans:", res, "\n")
        return {res.begin(), res.end()};
    }
};